package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-12-26 10:28:58	 当前时间
 */
//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 
//
// 有效 二叉搜索树定义如下： 
//
// 
// 节点的左子树只包含 小于 当前节点的数。 
// 节点的右子树只包含 大于 当前节点的数。 
// 所有左子树和右子树自身必须也是二叉搜索树。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [2,1,3]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目范围在[1, 104] 内 
// -231 <= Node.val <= 231 - 1 
// 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 1838 👎 0

public class 验证二叉搜索树{
	public static void main(String[] args) {
		Solution solution = new 验证二叉搜索树().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/7 11:18
	 */
	// 中序，看遍历的数组是否递增。
	// 记录上一个节点，看是否递增
	private TreeNode preNode = null;
	public boolean isValidBST(TreeNode root) {
		if (root==null){
			return true;
		}

		boolean left = isValidBST(root.left);
		if (preNode!=null){
			if (preNode.val>=root.val){
				return false;
			}
		}
		// 每次都需要记录上一个节点
		preNode = root;


		boolean right = isValidBST(root.right);

		return left&&right;

	}

	// 复习end




	// 中序
	TreeNode pre = null;
	public boolean isValidBSTDFS(TreeNode root) {
		if(root==null)return true;

		boolean  left = isValidBST(root.left);
		if(pre!=null){

			if(pre.val>=root.val){
				return false;
			}
			/**
			 * 这里不能直接else返回true
			 * 因为 遍历到此处只能说明目前是二叉搜索树
			 * 但  后面节点是否正确就不一定了，不能直接就确定。
			 * 需要遍历 一直到 叶子结点才可判断是否是搜索树
			 * 即： if(root==null) return true;
			 */

		}
		pre = root;
		boolean  right = isValidBST(root.right);
		return left&&right;


	}

	/**
	 * 中序遍历
	 */
//	TreeNode pre = null;
    public boolean isValidBST1(TreeNode root) {
 		if (root == null){
 			return true;
		}
		boolean	left = isValidBST(root.left);
		if (pre!=null&&pre.val>=root.val){
			return false;
		}
		// 记录 上一个节点
		pre = root;

		boolean	right = isValidBST(root.right);
		return left&&right;
    }

	/**
	 * |
	 *  0 1 2 3 4
	 *  4 5 3 6 7
	 *
	 */
	public boolean isValidBSTBFS(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		ArrayList<Integer> list = new ArrayList<>();
		if (root==null){
    		return true;
		}
    	while (!stack.isEmpty()||root!=null){
    		while (root!=null){
    			stack.push(root);
    			root = root.left;
			}
			TreeNode node = stack.pop();
    		list.add(node.val);
    		root = node.right;
		}
    	// 判断是否是递增数组
		for (int i = 1; i <= list.size()-1; i++) {
			if (list.get(i)<=list.get(i-1)){
				return false;
			}
		}
		return true;
	}


	/**
	 * 1 5 3 4 6
	 * 左中右
	 *
	 * | 4
	 *
	 * 1 5 3
	 *  中序遍历二叉搜索树： 为递增数组。
	 *  若不是则 不是二叉搜索树。
	 */
	public boolean isValidBSTBFS1(TreeNode root) {
		if (root==null){
			return true;
		}
		Stack<TreeNode> stack = new Stack<>();
		ArrayList<Integer> list = new ArrayList<>();
		TreeNode pre = null;
		while (!stack.isEmpty()||root!=null){
			if (root!=null){
				stack.push(root);
				root = root.left;
			}else{
				TreeNode node = stack.pop();
				list.add(node.val);
				if (pre!=null&&pre.val>=node.val){
					return false;
				}
				pre = node;
				root = node.right;
			}
		}
		System.out.println(list);
		return true;
	}

	/**
	 * 中序遍历的第二种写法
	 */
	public boolean isValidBST2(TreeNode root) {
		if (root==null){
			return true;
		}
		Stack<TreeNode> stack = new Stack<>();
		// 记录上一个节点
		TreeNode pre = null;
		while (!stack.isEmpty()||root!=null){
			 while (root!=null){
			 	stack.push(root);
			 	root = root.left;
			 }
			TreeNode node = stack.pop();
			 // 中序遍历不满足 递增(等于也不算递增) 则不是二叉搜索树
			 if (pre!=null&&pre.val>=node.val){
			 	return false;
			 }
			 pre = node;
			 root = node.right;
		}
		return true;

	}


	}
//leetcode submit region end(Prohibit modification and deletion)

}
